import com.sun.source.tree.Tree;

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode{
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }
        public TreeNode root;

        public void createTree(){
            TreeNode node1 =new TreeNode(11);
            TreeNode node2 =new TreeNode(12);
            TreeNode node3 =new TreeNode(13);
            TreeNode node4 =new TreeNode(14);
            TreeNode node5 =new TreeNode(15);

            node1.left=node2;
            node1.right=node3;
            node2.left=node4;
            node3.right=node5;
            root=node1;
        }

        public void preOrder(TreeNode root){
            if(root==null) return;
            System.out.print(root.value+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
        public void inOrder(TreeNode root){
            if(root==null) return;
            inOrder(root.left);
            System.out.print(root.value+" ");
            inOrder(root.right);
        }
        public void postOrder(TreeNode root){
            if(root==null) return;
             postOrder(root.left);
             postOrder(root.right);
             System.out.print(root.value+" ");
    }
    public int useSize;
    public void size1(TreeNode root){//直接遍历++
            if (root==null) return ;
            useSize++;
        size1(root.left);
        size1(root.right);
    }

    public int size2(TreeNode root){//直接遍历++
        if (root==null) return 0;
        int a=1;
        a+=size2(root.left)+size2(root.right);
        return a;
    }

    public int leafCount;
    public void getLeafNodeCount1(TreeNode root){
        if (root==null) return ;
        if(root.left==null&&root.right==null) leafCount++;
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }

    public int getLeafNodeCount2(TreeNode root){
        if (root==null) return 0;
        if (root.left==null&&root.right==null) return 1;
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }

    public boolean findValue(TreeNode root,int value){
        if (root==null) return false;
        if(root.value==value) return true;
        if(findValue(root.left,value)||findValue(root.right,value)) return true;
        return false;
    }

    public TreeNode invertTree(TreeNode root) {
        if(root==null) return null;
//        TreeNode left = root.left;
//        TreeNode right = root.right;
//        TreeNode node = root.left;
//        left = right;
//        right = node;
        TreeNode node=root.left;
        root.left=root.right;
        root.right=node;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public boolean isCompleteTree(TreeNode root){
        if(root==null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if (cur==null){
                while(!queue.isEmpty()){
                    if (queue.poll()!=null) return false;
                }
                return true;
            }
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        return true;
    }

//
}
